package 树;

public class 字节笔试根据后续结果还原二叉搜索树 {
    public static void main(String[] args) {

    }

    /**
     * 根据后续遍历结果，还原二叉搜索树
     * @param arr
     * @param l 数组的左指针
     * @param r 数组的右指针
     * @return 返回根节点
     */
    public static Node process(int[] arr,int l,int r){
        //1终止条件
        if (l > r){
            return null;
        }
        //否则存在节点
        Node root = new Node(arr[r]);
        //如果l==r说明是最后一个节点
        if (l == r) {return root;}

        //2否则数组存在多个数
        //根节点就是当前范围的r位置的值，由于是二叉搜索树，所以从l到r-1，找最后一个小于r的数，就是他的左孩子节点
        int M = l-1;//初始为l-1，如果没有比r小的数，说明都是r的右子树
        for (int i = l; i < r-1; i++) {
            if (arr[i] < arr[r]){
                M = i;
            }
//            if (arr[i] > arr[r]){
//                break;
//            }
        }
        //找到左右子树的分界
        //3那么当前节点的左右孩子递归调用
        root.left = process(arr,l,M);
        root.right = process(arr,M+1,r-1);
        //4返回结果
        return root;
    }

    //后续遍历
    public static void orderByLast(Node root){
        if (root == null){
            return;
        }
        orderByLast(root.left);
        orderByLast(root.right);
        System.out.println(root.val);
    }
}
